/*
 * @lc app=leetcode.cn id=454 lang=cpp
 *
 * [454] 四数相加 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int res = 0;
        // <sum, candidatesNum>
        std::unordered_map<int, int> candidates12;
        std::unordered_map<int, int> candidates34;
        for (int i=0;i<nums1.size();i++){
            for (int j=0;j<nums2.size();j++){
                int sum = nums1[i]+nums2[j];
                auto iter = candidates12.find(sum);
                if (iter == candidates12.end()){
                    candidates12.emplace(sum, 1);
                }else{
                    iter->second+=1;
                }
            }
        }
        for (int k=0;k<nums3.size();k++){
            for (int l=0;l<nums4.size();l++){
                int sum = nums3[k]+nums4[l];
                auto iter = candidates34.find(sum);
                if (iter == candidates34.end()){
                    candidates34.emplace(sum, 1);
                }else{
                    iter->second+=1;
                }
            }
        }
        for (auto& candidate12 : candidates12){
            int sum12 = candidate12.first;
            auto iter = candidates34.find(-sum12);
            if (iter != candidates34.end()){
                res += candidate12.second * iter->second;
            }
        }
        return res;
    }
};
// @lc code=end

